Denial of Service (DoS) attacks impose serious threats to the Internet, resulting in tremendous impact on our daily lives as they become increasingly dependent on the good health of the Internet. Presently, attackers are professionals who are involved in such activities because of financial incentives. Attack strategies and techniques are getting more sophisticated, and can evade conventional detection and defense. A low rate DoS attack is one example of this new breed of sophisticated attack to the Internet.
The concern over low rate DoS attack is commonly known. The 2006 CSI/FBI Computer Crime and Security Survey showed that denial of service (DoS) attacks are still an issue leading to a significant revenue loss for many organizations. The low rate DoS attack poses a new threat to the Internet including occurrences of these attacks on the Internet2 experimental network. Low rate DoS attacks first became publicly known in Kuzmanovic and Knightly, Low-Rate TCP-Targeted Denial of Service Attacks (The Shrew vs. the Mice and Elephants), ACM SIGCOMM 2003, 2003, pp. 75-86, but there has been no widely known solution or fix for them. It is also hard to defend against low rate DoS attacks as the current Internet lacks measures to detect and mitigate them automatically. The Reduction of Quality (RoQ) attack, or a low rate DoS attack that uses IP address spoofing, in particular does not try to shut down the legitimate flows, but tries to reduce the quality of service experienced by them. These attacks can evade detection because of their low average rates, i.e., the average amount of traffic required to stage such an attack is low. Adaptive queue management schemes like RED (random early detection) detect anomalous behavior based on the average queue lengths at the routers, and are therefore easily fooled by low rate DoS attacks. Thus, it is even harder to defend against RoQ attacks. All these low rate types of DoS attacks can be defined by a general periodic waveform as shown in FIG. 1. They are characterized by three parameters, the attack period (T), the burst period or the burst length (t), and the burst rate (R).
Low rate TCP DoS attacks exploit the minimum RTO (retransmission timeout) property of the TCP protocol. The following characterize a low rate TCP DoS attack:                It sends periodic bursts of packets at one-second intervals.        The burst rate is equal to or greater than the bottleneck capacity.        The burst period is tuned to be equal to the round-trip times of the TCP connections. The burst period determines whether the attack causes DoS to the TCP connections with small or long round trip times.        The exponential back off algorithm of the TCP's retransmission mechanism is eventually exploited.        
The RoQ (Reduction of Quality) attack targets to dampen QoS (Quality of Service) experienced by the TCP traffic by keeping the time period high. It tries to occupy the share of the legitimate network traffic by sending high rate bursts on longer timescales. The attacker can also keep the burst rate low to exacerbate the attack potency. For instance, by sending the periodic bursts of attack packets to a router, the attacker does not allow the queue to stabilize such that the QoS sensitive Internet traffic experiences degradation of quality. In particular, the periodicity is not well-defined in an RoQ attack, thereby allowing the attacker to keep the average rate of the attack traffic significantly low to evade the adaptive queue management techniques such as RED and RED-PD (random early detection packet drop). To distinguish the two attacks, an attack with time period less than or equal to one second is classified as a low rate DoS attack, while an RoQ attack is one with time period greater than one second. An RoQ attack is defined as an attack whose only objective is to reduce the quality of service received by an application. It may not cause denial of service, which is not its goal, but leads to reduction in quality of service. Note that the reduction of quality should be determined on a quality scale, which will be different for different applications. For simplicity, hereafter the term “low rate DoS attack” refers to both the low rate TCP DoS and RoQ attack, unless otherwise stated.
In previous detection systems, the detection system can detect the stealthy low rate TCP DoS attack by using a simple time difference method. The time difference technique uses a per-flow approach to store arrival times of the packets belonging to each flow, and computes inter-arrival times between the consecutive packets to detect periodicity. The attacker using IP address spoofing can easily deceive this simple per-flow approach as the time difference approach is not be able to detect periodicity in the attack flow, which is no longer a single flow. An attacker uses the IP address spoofing to fool the per flow detection system. Traditional approaches to mitigate the IP address spoofing such as IP traceback are useful when an end-host is attacked. However, the low rate DoS attack targets network elements, and so packets may not even reach the end host. The prior art has not addressed whether an individual router can detect spoofed packets used in a low rate DoS attack, and alleviate/mitigate both the spoofing and the low rate DoS attack. One embodiment described in the present application provides both detection and mitigation against the low rate DoS attacks. The detection part is memory intensive, and thus there is a scalable technique that passively detects the low rate DoS attack by using an algorithm, which works on the persistent memory. After having confirmed the onset of an attack, the filtering algorithm is enabled to separate long-lived legitimate flows at the router from attack flows, and subsequently drop these attack packets.
The MIT Spoofer project described in R. Beverly, S. Bauer, The Spoofer Project: Inferring the Extent of Source Address Filtering on the Internet, in: USENIX SRUTI'05, 2005, pp. 53-59, has reemphasized the detrimental effect of the IP address spoofing. Subnet IP address spoofing is easily orchestrated, as the ingress IP address filtering cannot contain the spoofing. To illustrate the subnet IP address spoofing, consider an attacker in the subnet, 12.28.34.0 to 12.28.34.100; an attacker can easily use any address in this range for spoofing a source IP address inside this subnet. The IP address of every outgoing packet can be spoofed by randomly selecting an IP address from the pool of IP addresses available for spoofing; this is referred to as random IP address spoofing. It is assumed that the attacker has complete control of the source machine and can change the operating system stack as needed. The attacker can use either the UDP or the TCP protocol to send a packet with any possible value in the packet header. The flow-id or a flow is defined by the combination of a source IP address, a destination IP address, a source port, and a destination port. The open knowledge of the RoQ attack and the ON-OFF periodic blasting attack shows that periodicity can be random for the low rate DoS attack. As described in Y. Xu, R. Guerin, On the Robustness of Router-based Denial-of-Service (DoS) Defense Systems, ACM Computer Communications Review. 35(3) 2005 47-60, the attacker has one IP address for every ON period; this is referred to as continuous cycle IP address spoofing. In this type of the attack, one flow consumes excessive bandwidth in order to exceed capacity of the bottleneck link in a short period of time (10-400 millisecond).
Considering the widespread use of botnets by attackers, it is not difficult for an attacker to use compromised machines with valid IP addresses to launch a low rate DoS attack. In addition, the master who controls botnets can sabotage machines in subnets scattered across the Internet. This causes the attack traffic rate coming out of each subnet to be not anomalous, however the aggregated traffic leads to DoS when it reaches the targeted router. Use of botnets also allows an attacker to use compromised machines to send attack traffic like random and continuous cycle IP address spoofing. In a low rate DoS attack, the required number of compromised machines is very low as compared to a traditional DDoS attack. In contrast, in a DDoS attack, the constant flooding of the link makes attack packets easily distinguishable. At least one feature not shown in the prior art is a system to mitigate low rate DoS attacks with IP address spoofing in which an attacker can employ different types of IP address spoofing strategies while launching a low rate DoS attack.